The pricing subproblem can be stated as follows: Find a feasible bin configuration with minimum reduced costs. The reduced cost of variable $j$ is defined as $\bar{c}_j = c_j - \sum_{i=1}^n p_i a_{ij}$ where $p_i, i \in N$ denotes the dual variable for the constraint regarding item $i$. Since $c_j=1$, minimizing $\bar{c}_j$ is equivalent to maximizing $\sum_{i=1}^n p_i a_{ij}$. This corresponds to the following IP:

\begin{align}
\max \quad & \sum_{i=1}^n p_i a_i \\
\mbox{s.t.} & \sum_{i=1}^n l_i a_i \leq W \\
& a_i \in \{0,1\} & j=1,\ldots,n
\end{align}

This is an integer knapsack programming that can be solved efficiently by dynamic programming or branch-and-bound. As long as the objective value is larger than 1, a new column is added to the original problem.

\medskip

We give the following example, where the extended formulation achieves a better LP bound than the original formulation: $W=3$, $L=\{2,2\}, N=\{1,2\}$.

If the integrality condition of the original formulation is relaxed, items can be split across multiple bins and the last bin is chosen to a fractional degree. Therefore the LP bound is given by $z^{\LP} = \frac{1}{W}\sum_{i=1}^n l_i$. For this instance $z^{\LP} = \frac{4}{3}$.

In the extended formulation, the set of feasible bin configurations is $C = \left\{\emptyset, \{1\}, \{2\} \right\}$. In order to satisfy constraint~\eqref{eq:ex8everyitem}, both non-empty bin configurations have to be chosen fully: $\lambda_{\{1\}} = \lambda_{\{2\}} = 1$ and the LP bound of the extended formulation $z_{\EX} = 2 > z^{\LP}$ is already the solution to the IP.

\medskip

It seems unreasonable to branch directly on the variables $\lambda_c, c \in C$ because the resulting branch-and-bound tree will be highly unbalanced. Instead, the branching rule should focus on the placement of items in order to eliminate more than one column in a new branch. Since the bins are not numbered, we cannot restrict the absolute placement of an item (e.g.\ item 2 is in bin 3). What we can do is to branch based on whether two items $i$ and $j$ are placed in the same bin or not. Formally, this means adding a constraint that ensures (respectively forbids) choosing a bin configuration containing both items $i$ and $j$:

\begin{align}
\sum_{\substack{c \in C \\ i,j \in c}} \lambda_c = 1.
\end{align}

This is added to the branch where $i$ and $j$ must be placed in the same bin. In the other branch the 1 is replaced by a 0. As a branching pair, we could use the pair $(i,j)$ where $\sum_{\substack{c \in C \\ i,j \in c}} \lambda_c$ is maximally fractional.